package com.qf.pojo.day01;

/**
 * @author lixu
 */
public class Demo {


    /**
     * 时间复杂度   O(2)  O(100)  O(n)  n：无穷大
     *   O(常量） 有数的
     *   n:规模  变量
     *
     *
     *   O(1)
     *
     * @return
     */
    public String test() {

        System.out.println("hello world"); // 需要执行 1 次



        return "你好"; // 需要执行 1 次



    }

    /**
     * 时间复杂度
     * O(n)
     *
     * f(n) = O(2n+1)  当n:无穷大
     *
     *
     * @return
     */
    public void test1(int N) {


        for (int i = 0; i < N; i++) {
            System.out.println("hello world1"); // 需要执行 N 次
            System.out.println("hello world2"); // 需要执行 N 次
        }


        System.out.println("hello world3"); // 需要执行 1 次
    }

    /**
     * O(n^2+n) = O(n^2)
     */
    public void test2(int N) {
        //循环1：时间复杂度为O(N^2)
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                System.out.println("hello world"); // 需要执行 N*N 次
            }
        }
        //循环2：时间复杂度为O(N)
        for (int i = 0; i < N; i++) {
            System.out.println("hello world1"); // 需要执行 N 次
        }
    }

    /**
     * 时间复杂度：
     *    最好：  O(n)
     *    最坏： O(n^2)
     * @param flag
     * @param N
     */
    public void test4(boolean flag,int N) {
        if(flag){
            //循环1：时间复杂度为O(N^2)
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    System.out.println("hello world"); // 需要执行 N*N 次
                }
            }
        }else{
            //循环2：时间复杂度为O(N)
            for (int i = 0; i < N; i++) {
                System.out.println("hello world1"); // 需要执行 N 次
            }
        }

    }

    /**
     *  O(1) == 基本上没有传递规模
     *  O(n)
     *  O(n^2)
     * @param arr
     * @return
     */
    public static int[] bubbleSort(int[] arr) {
        if (arr == null || arr.length < 2) {// 执行1行
            return arr;//1行
        }
        int n = arr.length;//1行
        for (int i = 0; i < n; i++) {// n行   7行
            boolean flag = true;
            for (int j = 0; j < n -i - 1; j++) {// n行
                if (arr[j + 1] < arr[j]) {
                    flag = false;
                    int t = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = t;
                }
            }
            //一趟下来是否发生位置交换
            if(flag)
                break;
        }
        return arr;
    }
}
